Dijkstra's algorithm can be expressed formally as follows:
G - arbitrary connected graph
v0 - is the
initial beginning vertex
V - is the set of all vertices in
the graph G
S - set of all vertices with permanent labels
n - number of vertices in G
D
- set of distances to v0
C - set of edges in G
Dijkstra Algorithm (graph G, vertex v0)
{
S={v0}
For i = 1 to n
D[i] = C[v0,i]
For i = 1 to n-1
Choose a vertex w in V-S such
that D[w] is minimum
Add w
to S
For each vertex v in
V-S
D[v] = min(D[v], D[w] + C[w,v])
}
![]() Back to Dijkstra's Algorithm |
![]() On to Flow Problems |